package LinkList;

  //Definition for singly-linked list.
  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
     //思路1，倒数第i个，就是顺数n-i个但是得遍历两遍
        int count = 0;
        ListNode tmp = head;
        while (tmp!=null)
        {
            count= count+1;
            tmp = tmp.next;
        }
        int i = count-n;
        ListNode DumpNode = null;
        DumpNode.next = head;
        ListNode pre = DumpNode;
        ListNode cur = head;

        int j = 0;
        while (j<i)
        {
            pre = cur;
            cur = cur.next;
            j++;
        }
        pre.next = cur.next;
        return DumpNode.next;
    }
}
public class item19 {
    public ListNode removeNthFromEnd1(ListNode head, int n)
    {//思路2：双指针思路，第一个指向头结点，第二个指向第n个节点，当第二个节点走向末尾的时候
        //第一个节点就正好到倒数第n个节点
        int i= 0;
        ListNode first = head;
        ListNode second = head;
        while (i<n)
        {
            i++;
            second = second.next;
        }
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode pre = fakeHead;
        while (second!=null)
        {   pre = first;
            first = first.next;
            second = second.next;
        }
        pre.next = first.next;
        return  fakeHead.next;
    }
}
